Computer programs that perform logic synthesis are known. These computer programs generally use mathematical techniques that do not have general solutions. The classic example of the type of mathematical problem that does not have a general solution is the "traveling salesman"problem.
Faced with the lack of a rigorous mathematical solution, logic design engineers have had to develop techniques which may not be mathematically rigorous but which do produce acceptable results. Such techniques generally involve compromises and practical limitations.
The design of VLSI integrated circuits presents a number of challenges beyond those encountered in the design and development of smaller integrated circuit chips. A longer manufacturing cycle, tighter timing requirements, shorter machine cycle, and a larger number of gates per designer all must be overcome while a shorter development time is also desired. In order to produce a modern design, modern tools must be used.
One of the tools becoming increasingly common in logic design is synthesis. Logic synthesis addresses many problems, one of them being the conversion of a more-or-less technology independent register transfer (RT) design model to a technology dependent model. Many of the existing logic synthesis programs begin by having the designer describe the desired logical function in a high level "register transfer"language such as "Very High Speed Integrated Circuit (VHSIC) Hardware Description Language" (commonly referred to as VHDL). VHDL is a register transfer design language used by many government contractors.
Logic synthesis can also be used to generate a technology dependent model from a very high level (e.g. higher than RT) description or to convert a technology dependent design to a different technology. The former use is currently more theoretical than practical while the latter use is of limited value in certain situations due to the nature of certain designs. The term "logic synthesis"shall be used herein to mean the synthesis of a technology dependent model from an RT description.
The successful use of logic synthesis in the computer industry is becoming more and more common. Synthesis has been successfully used in the design of the a modern computer as described in a paper by Y. Tsuchiya, M. Morita, Y. Ikariya, E. Tsurumi, T. Mori, T. Yanagita,"Establishment of higher level logic design for very large scale computer," Twenty-third Design Automation Conference:, Las Vegas, Nev., 1986, pp. 366-371.
A paper by D. Gregory, K. Bartlett, A. de Geus, G. Hachtel, entitled "SOCRATES: A system for automatically synthesizing and optimizing combinational logic," Twenty-third Design Automation Conference, Las Vegas, Nev., 1986, pp. 79-85, has reported very good results in the use of their logic synthesis tool, For example in one experiment cited in this reference an ALU circuit TTL schematic was provided to an experienced designer and to the described system and both were given the task of optimizing the circuit for speed. The manual design overall performance was less than one percent better than the design from the automated system. However, the automated system generated its design in two CPU hours compared with six weeks for the manual design.
The existing logic synthesis programs generally operate as follows: They use a register transfer language description as input. This input is provided by a logic designer. The set of register transfer expressions written by the designer are parsed into tokens. Next these tokens are converted to a set of primitive boolean function blocks. Logic reduction transformations are then performed on this global set of primitive blocks.
One problem encountered while synthesizing a design is providing the same level of information to the logic synthesis system as would be available to a human designer. Much of the information available to a designer, however, does not exist in any computer-readable form. Yet, a Register Transfer (RT) description contains a great deal of information in the form of the logic structure which could be used by the logic synthesis tool.
Typically, as the RT description is processed in preparation for logic synthesis, the model is reduced to primitive form, thus destroying most of the structural information contained in the original description. This is done to place fewer restrictions on the logic reduction programs but experiments have shown that structural restrictions based on external broad-based knowledge (i.e. global information possessed by the designer and injected into the synthesis system via structure) produce better results. Compounding the problem of structural information loss, RT list languages often are degraded to a very primitive dyadic form making preservation of the structural information more difficult than for other description forms (graphics descriptions, for example).
With the present invention, innovations in the techniques for processing the output of a parser prior to and during the logic synthesis process have made it possible to preserve the designers original structure to a very large extent. One of the primary benefits this provides is that changes to the synthesized design may be effected in a predictable manner by modifying the original RT description.
There is a great deal of prior art relating to the problem of developing efficient logical synthesis programs. For example, there is an annual Design Automation Conference and the Proceedings of these conferences are regularly published. Twenty three such conferences have been held. The proceedings of the Twenty Third Conference where published in 1986. The proceedings of the annual Design Automation Conferences document the state of the art in this general area.
A book entitled Design Automation of Digital Systems, M. A. Breuer editor, Prentice Hall Inc.,(1972), and a book by F. J. Hall and G. R. Peterson, Digital Systems: Hardware Organization and Control, John Wiley & Sons Inc, New York 1973, provides an overview of the early developments.
A paper by J. R. Duley and D. L. Dietmeyer, "Translation of a DDL Digital System Specification to Boolean Equations," IEEE Transactions Computer C-18, 305-320 (1969) also provides background perspective about some of the early work.
A paper entitled "Logic Systhesis Through Local Transformations" by John Darringer, William Joyner, C. Derman and Louise Trevillyan, published in the IBM Journal of Research and Development Vol 25 No 4, page 272-280, July 1981 shows some examples of known logic reduction techniques.
A paper by D. Gregory, K. Bartlett, A. de Geus, and G. Hachtel, entitled "Socrates: A system for automatically synthesizing and optimizing combinational logic" Twenty Third Design Automation Conference" Las Vegas, Nev. 1986, pp. 79-85, describes an example of existing logic synthesis programs.
A paper by W. Joyner, L. Trevillyan, D. Brand, T. Nix and S. Gundersen, entitled "Technology adaptation in Logic Synthesis" Twenty third Design Automation Conference"Las Vegas, Nev., 1986, pp 94-100 shows an example of converting expressions to primitive prior to logic reduction.